/*
 * Copyright (c) [2022] [王鹏欢]
 *    [DataStructure] is licensed under Mulan PSL v2.
 *    You can use this software according to the terms and conditions of the Mulan PSL v2.
 *    You may obtain a copy of Mulan PSL v2 at:
 *             http://license.coscl.org.cn/MulanPSL2
 *    THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 *    See the Mulan PSL v2 for more details.
 */

package com.huan.sparseArray;


/**
 * 稀疏数组
 *
 * @Author 王鹏欢
 * @Date 2021-09-07 8:54
 */
public class SparseArray {
    public static void main(String[] args)
    {
        //创建一个二维数组，11*11的规格
        //0:表示没有棋子， 1：黑子 2：蓝子
        int[][] chessArr = new int[11][11];
        /**
         * @description: 存入数据
         */
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[4][5] = 2;
        //输出原有的二维数组
        System.out.println("输出原有的二维数组");
        //遍历二维数组
        for (int[] its : chessArr) {
            for (int it : its) {
                //输出数据加空格符
                System.out.print(it + "\t");
            }
            //换行
            System.out.println();
        }


        //将二维数组转为稀疏数组
        int sum = 0;//获取非0的个数
        //先遍历二维数组
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;//非0个数
                }
            }
        }
        /**
         * @description: 一共非0个数+1列，三行（固定）
         *    二维数组的行数     二维数组的列数     非0的个数
         *         11          	11          	3
         *      非0数的行数(+1)  非0数的列数(+1)  非0数的值
         *         1           	2           	1
         *         2           	3           	2
         *         4           	5           	2
         */
        //2.创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;//第一行第一列为二维数组的行数
        sparseArr[0][1] = 11;//第一行第二列为二维数组的列数
        sparseArr[0][2] = sum;//第一行第三列为二维数组非0数的个数
        //遍历二维数组，将非0的数存入稀疏数组sparseArr中
        int count = 0;//用于记录 当前数据是第几个非0的数据
        //遍历
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                //当二维数组不为0时
                if (chessArr[i][j] != 0) {
                    count++;
                    //第一列为行数
                    sparseArr[count][0] = i;
                    //第二列为列数
                    sparseArr[count][1] = j;
                    //第三列为二维数组的具体数
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        // 输出稀疏数组的形式
        System.out.println();
        System.out.println("得到稀疏数组为~~~~");
        //遍历稀疏数组得到图形
        for (int[] its : sparseArr) {
            //输出三个值后换行
            System.out.println(its[0] + "\t" + its[1] + "\t" + its[2]);
        }
        System.out.println();


        //将稀疏数组 --> 恢复成 原始的二维数组
        /** 1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
         2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
         */
        //1. 先读取稀疏数组的第一行和第二个值(二维数组的规格)，根据第一行的数据，创建原始的二维数组
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        //System.out.println(sparseArr.length);  (稀疏数组长度为稀疏数组的行数)
        for (int i = 1; i < sparseArr.length; i++) {
            /**
             * @description: sparseArr[i][2]
             * 恢复后的二维数组的位置===稀疏数组的第二行第一列[1]、第二行第二列为[2]==值为稀疏数组第二行的第三个数据（具体的值）
             */
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];//将具体的值填入恢复后二维数组的位置上
        }
        // 输出恢复后的二维数组
        System.out.println();
        System.out.println("恢复后的二维数组");
        for (int[] its : chessArr2) {
            for (int i : its) {
                //输出（+空格）
                System.out.print(i + "\t");
            }
            System.out.println();
        }
    }

}
